/*
    Geocache: some utilities for managing and visualizing geocache information
    Copyright (C) 2008  Gary Jackson

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
/*
 * PointSet.java
 */

package com.thegbomb.sphere;

import com.thegbomb.common.CircleList;
import com.thegbomb.common.LinkedCircleList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 *
 * @author Gary Jackson
 */
public class PointSet implements Set<Point> {
    private Set<Point> backing;
    private Point centroid;
    
    /**
     * Creates a new instance of PointSet
     */
    public PointSet(Set<Point> contents) {
        this.backing = Collections.unmodifiableSet(contents);
        
        Cartesian accumulator = new Cartesian(0, 0, 0);
        for (Point p: backing) {
            accumulator = accumulator.add(p.getCartesian());
        }
        
        this.centroid = new Point(accumulator.sdiv(backing.size()).normalize());
    }
    
    public boolean addAll(Collection<? extends Point> c) {
        throw new UnsupportedOperationException();
    }
    
    public boolean contains(Object o) {
        return backing.contains(o);
    }
    
    /** {@inheritDoc} */
    public boolean equals(Object obj) {
        if (obj instanceof PointSet) {
            PointSet ps = (PointSet)obj;
            boolean value = this.backing.equals(ps.backing);
            return value;
        }
        
        return false;
    }
    
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }
    
    public <T> T[] toArray(T[] a) {
        return backing.toArray(a);
    }
    
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }
    
    public boolean containsAll(Collection<?> c) {
        return backing.containsAll(c);
    }
    
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }
    
    public boolean add(Point o) {
        throw new UnsupportedOperationException();
    }
    
    public Object[] toArray() {
        return backing.toArray();
    }
    
    public int size() {
        return backing.size();
    }
    
    public void clear() {
        throw new UnsupportedOperationException();
    }
    
    protected Object clone() throws CloneNotSupportedException {
        return this;
    }
    
    public boolean isEmpty() {
        return backing.isEmpty();
    }
    
    public Iterator<Point> iterator() {
        return backing.iterator();
    }
    
    public Point getCentroid() {
        return centroid;
    }
    
    public PointSet rotate(Point axis, double angle) {
        Set<Point> s = new HashSet<Point>();
        for (Point p : backing) {
            s.add(p.rotate(axis, angle));
        }
        return new PointSet(s);
    }
    
    public Polygon convexHull() {
        if (this.size() < 4)
            return new Polygon(new LinkedList<Point>(this));
        
        Set<Point> operating = this;
        
        Comparator<Point> lexical = new Comparator<Point>() {
            public int compare(Point o1, Point o2) {
                if (o1.getPhi() == o2.getPhi())
                    return Double.compare(o1.getTheta(), o2.getTheta());
                else
                    return Double.compare(o1.getPhi(), o2.getPhi());
            }
        };
        
        Point axis = Point.NORTH_POLE.normal(centroid);
        double angle = -centroid.distance(Point.NORTH_POLE);
        
        // If the centroid is not the north pole
        if (! centroid.equals(Point.NORTH_POLE)) {
            operating = this.rotate(axis, angle);
        }
        
        Point sequence[] = operating.toArray(new Point[0]);
        Arrays.sort(sequence, lexical);
        
        LinkedList<Point> compressed = new LinkedList();
        Point cur = sequence[0];
        compressed.add(cur);
        for (int i = 1; i < sequence.length; i++) {
            if (sequence[i].getPhi() == cur.getPhi()) {
                if (sequence[i].getTheta() < cur.getTheta())
                    throw new RuntimeException("Houston, we have a problem");
            } else {
                cur = sequence[i];
                compressed.add(cur);
            }
        }
        
        CircleList<Point> seq = new LinkedCircleList<Point>();
        LinkedList<Point> acc = new LinkedList<Point>();
        
        Point max = compressed.removeFirst();
        double maxDist = max.distance(Point.NORTH_POLE);
        while (!compressed.isEmpty()) {
            Point tmp = compressed.removeFirst();
            double distance = tmp.distance(Point.NORTH_POLE);
            if (distance == 0)
                continue;
            if (distance > maxDist) {
                seq.insertPrevious(max);
                seq.addAll(acc);
                acc.clear();
                max = tmp;
                maxDist = distance;
            } else {
                acc.addLast(tmp);
            }
        }
        
        while (! acc.isEmpty()) {
            seq.insertNext(acc.removeLast());
        }

        if (maxDist > Math.PI/2)
            throw new SphereException("set is not in Euclidean position");        
        
        int size = seq.size();
        Point current[] = { max, seq.removeNext(), seq.removeNext()};
        boolean ready = false;
        while (true) {
            Orthodrome a = new Orthodrome(current[0], current[2]);
            Orthodrome b = new Orthodrome(Point.NORTH_POLE, current[1]);
            if (a.intersects(b, Util.TOLERANCE)) {
                seq.insertPrevious(current[0]);
                current[0] = current[1];
                current[1] = current[2];
                current[2] = seq.removeNext();
                if (current[2] == max) {
                    ready = true;
                }
                if (ready && current[0] == max) {
                    seq.insertPrevious(current[0]);
                    seq.insertPrevious(current[1]);
                    seq.insertPrevious(current[2]);
                    break;
                }
            } else {
                current[1] = current[0];
                current[0] = seq.removePrevious();
            }
        }
        
        List<Point> ret = new LinkedList<Point>();
        for (Point p: seq) {
            if (centroid.equals(Point.NORTH_POLE)) {
                ret.add(p);
            } else {
                if (p instanceof RotatedPoint)
                    ret.add(((RotatedPoint)p).getOriginal());
                else
                    ret.add(p.rotate(axis, -angle));
            }
        }
        
        return new Polygon(ret);
    }
    
    public String toString() {
        StringBuffer buf = new StringBuffer("{ ");
        for (Point p: backing) {
            buf.append(p);
            buf.append(" ");
        }
        buf.append("}");
        return buf.toString();
    }
}
